package com.michael.leetcode;

import org.junit.Test;

import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class RemoveInterval_1272 {
    public List<List<Integer>> removeInterval1(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> res = new ArrayList<>();

        int[] f = new int[intervals.length];
        int[] t = new int[intervals.length];
        for(int i = 0; i < intervals.length ; i++) {
            f[i] = intervals[i][0];
            t[i] = intervals[i][1];
        }
        int st = stors(f, toBeRemoved[0]);
        int en = stors(t, toBeRemoved[1]);

        // 第一种情况 col[st] = toBeRemoved[0]  或者 col[st] > toBeRemoved[0] > col[st-1] 或者 col[st] < toBeRemoved[0] < col[st+1]
        for(int i = 0; i < intervals.length ; i++) {
            if (i < st){
                List<Integer> tmp = new ArrayList<>(2);
                tmp.add(intervals[i][0]);
                tmp.add(intervals[i][1]);
                res.add(tmp);
            }else if (i == st){
                if (intervals[i][0] < toBeRemoved[0]){
                     List<Integer> tmp = new ArrayList<>(2);
                    tmp.add(intervals[i][0]);
                    tmp.add(toBeRemoved[0]);
                    res.add(tmp);
                }
            }
        }



        return res;
    }

    public int stors(int[] arrs, int targe){
        int start = 0;
        int end = arrs.length-1;
        while (start < end){
            int mid = (end+start)/2;
            if (arrs[mid] > targe){
                end = mid-1;
            }else if(arrs[mid] < targe){
                start = mid+1;
            }else {
                // 第一组 0 到 l1
                 return mid;
            }
        }
        return start;
    }

    /**
     * 1272. 删除区间
    实数集合可以表示为若干不相交区间的并集，其中每个区间的形式为 [a, b)（左闭右开），表示满足 a <= x < b 的所有实数  x 的集合。如果某个区间 [a, b) 中包含实数 x ，则称实数 x 在集合中。
    给你一个 有序的 不相交区间列表 intervals 。intervals 表示一个实数集合，其中每一项 intervals[i] = [ai, bi] 都表示一个区间 [ai, bi) 。再给你一个要删除的区间 toBeRemoved 。
    返回 一组实数，该实数表示intervals 中 删除 了 toBeRemoved 的部分 。换句话说，返回实数集合，并满足集合中的每个实数 x 都在 intervals 中，但不在 toBeRemoved 中。你的答案应该是一个如上所述的 有序的 不相连的间隔列表 。

    示例 1：
    输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
    输出：[[0,1],[6,7]]
    *
    示例 2：
    输入：intervals = [[0,5]], toBeRemoved = [2,3]
    输出：[[0,2],[3,5]]
    *
    示例 3：
    输入：intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
    输出：[[-5,-4],[-3,-2],[4,5],[8,9]]

    提示：
    1 <= intervals.length <= 104
    -109 <= ai < bi <= 109
     */
    // 思路是遍历 只需要考虑 intervals中每一段和 toBeRemoved 的关系就可以
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> res = new ArrayList<>();
        int l = toBeRemoved[0];
        int r = toBeRemoved[1];

        for (int[] a : intervals ) {
            int x = a[0];
            int y = a[1];

            if (l > x ){
                res.add(new ArrayList<>(Arrays.asList(x, Math.min(y, l))));
            }

            if (r < y) {
                res.add(new ArrayList<>(Arrays.asList(Math.max(x, r), y)));
            }

        }

        return res;
    }


    @Test
    public void test(){
        int[][] intervals = {{0,2},{3,4},{5,7}};
        int[] toBeRemoved = {1,6};

        removeInterval(intervals, toBeRemoved);

    }



}